/*
 * @lc app=leetcode.cn id=4 lang=cpp
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lc code=start
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m == 0) {
            if(n % 2 == 1) {
                return double(nums2[n/2]);
            }else {
                return double(nums2[n/2]+nums2[n/2 - 1])/2.0;
            }
        }
        if(n == 0) {
            if(m % 2 == 1) {
                return double(nums1[m/2]);
            }else {
                return double(nums1[m/2]+nums1[m/2 - 1])/2.0;
            }
        }
        int sum = m + n;
        vector<int> arr;
        int ptr1 = 0,ptr2 = 0;
        while(ptr1 < m && ptr2 < n) {
            if(nums1[ptr1] < nums2[ptr2]) {
                arr.push_back(nums1[ptr1]);
                ptr1++;
            }else {
                arr.push_back(nums2[ptr2]);
                ptr2++;
            }
        }
        while(ptr1 < m) {
            arr.push_back(nums1[ptr1]);
            ptr1++;
        }
        while(ptr2 < n) {
            arr.push_back(nums2[ptr2]);
            ptr2++;
        }
        if(sum % 2 == 1) {
            return double(arr[sum/2]);
        }else {
            return double(arr[sum/2] + arr[sum/2-1])/2.0;
        }
    }
};
// @lc code=end


// double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//         int m = nums1.size(),n = nums2.size();
//         int l = 0,r = 0;
         //可以在数组整合到一半时出来，降低时间复杂度
//         int i = 0;
//         vector<int> res;
//         while(l < m && r < n) {
//             if(nums1[l] < nums2[r]) {
//                 res.push_back(nums1[l]);
//                 l++;
//                 i++;
//             } else {
//                 res.push_back(nums2[r]);
//                 r++;
//                 i++;
//             }
//             if(i > (m+n)/2) {
//                 break;
//             }
//         }
//         if(l == m) {
//             for(int i = r;i < n;i++) {
//                 res.push_back(nums2[i]);
//             }
//         }else {
//             for(int i = l;i < m;i++) {
//                 res.push_back(nums1[i]);
//             }
//         }
//         int len = m + n;
//         double ans = 0.0;
//         if(len % 2 == 1) {
//             ans = double(res[len/2]);
//         }else {
//             ans = (double(res[len/2]) + double(res[len/2 - 1]))/2;
//         }
//         return ans;
//     }
